package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author tzp
 * @since 2020/9/14
 */
public class LC404 implements TreeProblem {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        Deque<TreeNode> xx = new ArrayDeque<>();
        xx.add(root);
        int sum = 0;
        while (xx.size() != 0) {
            TreeNode node = xx.pollFirst();
            if (node.right != null) {
                xx.addFirst(node.right);
            }
            if (node.left != null) {
                xx.addFirst(node.left);
                if (node.left.left == null && node.left.right == null) {
                    sum += node.left.val;
                }
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        {
            TreeNode node3 = new TreeNode(3);
            TreeNode node9 = new TreeNode(9);
            TreeNode node20 = new TreeNode(20);
            TreeNode node15 = new TreeNode(15);
            TreeNode node7 = new TreeNode(7);
            node3.left = node9;
            node3.right = node20;
            node20.left = node15;
            node20.right = node7;

            System.out.println(new LC404().sumOfLeftLeaves(node3));
        }
        {
            TreeNode node1 = new TreeNode(1);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(3);
            TreeNode node4 = new TreeNode(4);
            TreeNode node5 = new TreeNode(5);
            node1.left = node2;
            node1.right = node3;
            node2.left = node4;
            node2.right = node5;

            System.out.println(new LC404().sumOfLeftLeaves(node1));
        }

    }
}
